Inventer des légendes qui satisfont tous les participants de l'UJGOI est une tâche énorme.
C'est pourquoi cette légende a été volée.
Vous disposez d'un graphe dirigé avec sommets qui est initialement vide. À partir de la première seconde, pendant chaque seconde, une arête dirigée est ajoutée à ce graphe.
Votre tâche est de traiter requêtes.
Chaque requête est donnée par deux nombres et . Votre tâche est de déterminer le premier moment où il existe un chemin de à et de à .
Si même après que toutes les arêtes aient été ajoutées, il n'y a pas de chemin de à ou de à , vous devez afficher .
De plus, si x=y, vous devez afficher .
La première ligne contient quatre entiers n,m,q,t (1\le n,m,q\le 3\cdot 10^5; t \in \{0,1\}).
Chacune des lignes suivantes contient deux entiers v_i et u_i (1 \leq v_i, u_i \leq n) — les arêtes qui sont ajoutées à un graphe initialement vide dans l'ordre où elles sont ajoutées.
Chacune des lignes suivantes contient deux entiers et (1\le x, y \le n), qui désignent une requête.
Lorsque t=0, chaque requête est donnée sans encodage.
Lorsque t=1, chaque requête est donnée avec encodage :
initialement, key=0. Lorsque vous recevez les entiers dans une requête, vous formez les entiers ;
x=(key-1 + a) \mod n+1 ;
y=(key-1 + b) \mod n+1 ;
après cela, vous répondez à la requête ; laissez être la réponse à cette requête, puis vous mettez à jour key = ans avant de répondre à la prochaine requête.
Pour chaque requête, affichez la réponse.
Example 1
Example 2
Le graphe pour les deux exemples. Chaque arête a une étiquette qui indique le moment où elle a été ajoutée. Notez que le deuxième exemple est crypté ; après une description correcte, vous vous retrouvez avec les mêmes requêtes que dans le premier cas de test.
Pour les nœuds , il n'est pas difficile de voir que seulement lorsque toutes les arêtes jusqu'à la 6^{ème} sont présentes, il existe un chemin de à et de à .
Pour les nœuds , même lorsque toutes les arêtes sont présentes, il n'y a pas de chemin de à .
Pour les nœuds , seulement lorsque toutes les arêtes sont présentes, il existe un chemin de à et de à .
Pour les nœuds , même lorsque toutes les arêtes sont présentes, il n'y a pas de chemin de à .
Pour les nœuds , seulement lorsque toutes les arêtes sont présentes, il existe un chemin de à et de à .
( points) : n,m\le 80, t = 0 ;
( points) : n,m\le 10^3, t = 0 ;
( points) : q \le 100, t = 0 ;
( points) : t = 0 ;
( points) : sans contraintes supplémentaires.