[Solution] Building Forest Trails solution codeforces | ICPC WF Moscow Invitational Contest

Building Forest Trails solution codeforces

There are nn villages lying equidistant on a circle in the middle of a thick, impassable forest. From ancient times, it was impossible to move from one village to another, but technical progress has changed a lot. Now, there is a technology to build passable trails in the forest.

The building process consists of mm events. Each event is either building a trail or querying if two villages are connected. Trails are built as straight lines connecting two villages. After a trail is built, anybody can walk along the trail from one village to another.

Moreover, if two trails cross, anybody can turn at the intersection, and if other trails leave a village you have just reached, they can also be used to walk along. So, for example, if villages are numbered 11 to 66 in the order around the circle, and there are trails 11 to 3322 to 44, and 44 to 66, then all villages, except the 55-th, are reachable from the 11-st village.

Given a list of mm events, for each query, find if two given villages are reachable from each other at that moment.

Building Forest Trails solution codeforces

Input

The first line contains two integers nn (2n21052≤n≤2⋅105) and mm (1m31051≤m≤3⋅105) — the number of villages and the number of events respectively.

Next mm lines contain events. Each event description consists of three integers ee (ee is 11 or 22), vv (1vn1≤v≤n), and uu (1un1≤u≤nuvu≠v). If e=1e=1, then the event is building a trail between villages vv and uu. If e=2e=2, then the event is a query if the villages vv and uu are connected. It is guaranteed that each trail is built at most once.

Villages are numbered 11 to nn in clockwise order around the circle.

Building Forest Trails solution codeforces

Output

For each query print one character ‘0‘ if villages are not reachable, and ‘1‘ if villages are reachable from each other. Print answers for all queries as a single string in one line.

Building Forest Trails solution codeforces

Examples

input

Copy
6 9
1 1 3
1 4 6
2 3 4
1 2 4
2 1 2
2 1 3
2 1 4
2 6 1
2 5 3
output

Copy
011110

Building Forest Trails solution codeforces

input

Copy
2 5
2 1 2
2 2 1
1 1 2
2 1 2
2 2 1

Building Forest Trails solution codeforces

output

Copy
0011

 


 

Building Forest Trails solution codeforcesYet another MEX problem solution codechefYet another MEX problem solution codechefYet another MEX problem solution codechef

Leave a Comment