Լեգենդներ մտածելը, որոնք բավարարում են բոլոր UJGOI մասնակիցներին, բարդ գործ է:
Այդ պատճառով այս լեգենդը գողացվեց:
Դուք ստանում եք ուղղորդված գրաֆ, որի մեջ գագաթներ կան, որը սկզբում դատարկ է: Առաջին վայրկյանից սկսած, յուրաքանչյուր վայրկյան, այս գրաֆին ավելացվում է ուղղորդված կող:
Ձեր առաջադրանքն է մշակել հարցում:
Յուրաքանչյուր հարցման մեջ տրվում է երկու թիվ և : Ձեր առաջադրանքն է որոշել ժամանակի առաջին պահը, երբ -ից -ին և -ից -ին անցնելու ճանապարհ կա:
Եթե նույնիսկ բոլոր կողերը ավելացվելուց հետո -ից -ին կամ -ից -ին ճանապարհ չկա, դուք պետք է արտածեք :
Նաև, եթե x=y, դուք պետք է արտածեք :
Առաջին տողում տրված են չորս ամբողջ թվեր՝ n,m,q,t (1\le n,m,q\le 3\cdot 10^5; t \in \{0,1\}):
Հաջորդ տողերից յուրաքանչյուրը պարունակում է երկու ամբողջ թիվ՝ v_i և u_i (1 \leq v_i, u_i \leq n) — կողերը, որոնք ավելացվում են սկզբում դատարկ գրաֆում այն կարգով, որով դրանք ավելացվում են:
Հաջորդ տողերից յուրաքանչյուրը պարունակում է երկու ամբողջ թիվ՝ և (1\le x, y \le n), որոնք նշում են հարցումը:
Երբ t=0, յուրաքանչյուր հարցում տրվում է առանց կոդավորման:
Երբ t=1, յուրաքանչյուր հարցում տրվում է կոդավորմամբ:
սկզբում, key=0: Երբ հարցման մեջ ձեզ տրվում են ամբողջ թվեր , դուք ձևավորում եք ամբողջ թվեր ;
x=(key-1 + a) \mod n+1;
y=(key-1 + b) \mod n+1;
դրանից հետո, դուք պատասխանեք հարցմանը; թող լինի այս հարցման պատասխան, ապա դուք թարմացնում եք key = ans հաջորդ հարցմանը պատասխանելուց առաջ:
Յուրաքանչյուր հարցման համար, արտածեք պատասխանը:
Example 1
Example 2
Գրաֆը երկու օրինակների համար: Յուրաքանչյուր կող ունի պիտակ, որը նշում է ժամանակի պահը, երբ այն ավելացվել է: Նշենք, որ երկրորդ օրինակը կոդավորված է; ճիշտ ապակոդավորումից հետո, դուք կստանաք նույն հարցումները, ինչ առաջին թեստի դեպքում:
Գագաթների համար դժվար չէ տեսնել, որ միայն երբ բոլոր կողերը մինչև 6-րդ առկա են, կա ճանապարհ -ից -ին և -ից -ին:
Գագաթների համար նույնիսկ երբ բոլոր կողերը առկա են, չկա ճանապարհ -ից :
Գագաթների համար միայն երբ բոլոր կողերը առկա են, կա ճանապարհ -ից -ին և -ից -ին:
Գագաթների համար նույնիսկ երբ բոլոր կողերը առկա են, չկա ճանապարհ -ից :
Գագաթների համար միայն երբ բոլոր կողերը առկա են, կա ճանապարհ -ից -ին և -ից -ին:
( միավոր): n,m\le 80, t = 0;
( միավոր): n,m\le 10^3, t = 0;
( միավոր): q \le 100, t = 0;
( միավոր): t = 0;
( միավոր): առանց լրացուցիչ սահմանափակումների.