Phát has a very hard-working little sister. However, history seems to be the subject that poses an obstacle for her, so Phát has to help her with this. Today, our two friends will review the history of technology and how it impacts innovations throughout countries.

As we have already known, there are ~n~ countries in the world, developing independently of each other. Phát will help his sister review a few core events:

• The first important is the development of aviation. Today, air travel remains one of the fastest and safest forms of transportation. The construction of airports and aviation sites is imperative for a technologically developed country. At some point, a straight flight route will be opened between two countries ~u~ and ~v~. After this event, people can fly from country ~u~ to country ~v~, and vice-versa.

• Global collaboration is also an important aspect of technological development. At some point, two countries ~x~ and ~y~ will sign a partnership agreement in technology.

• Perhaps the most noteworthy event is an innovation. When a country ~k~ develops a novel technology, said the country will invite diplomats, as well as engineers from other countries that it has signed a partnership with, to come to country ~k~ for a seminar on this latest technology. However, seminar events are on short notice, so guests will have to take the plane to reach the event. Air traveling is fast, and thus guests can take multiple flights, and travel through intermediate countries if needed, to reach their destination country. However, if a country ~h~ receives an invitation from country ~k~, yet there is no way to air-travel to country ~k~ from country ~h~, then country ~h~ will not send delegations to the event.

Phát has recited for his sister ~q~ events in chronological order. However, the little sister still has trouble remembering all these pieces of information. He poses a riddle to help her sister remember these more easily: for each seminar, how many countries will send their people to attend that seminar.

Given that there are ~n~ independent countries. Initially, there were no direct flights from one country to another, and there have been no signed partnership agreements. Given the list of ~q~ events in chronological order, can you help Phát's little sister answer the riddle for each seminar event?

Input

The first line contains two integers ~n~ and ~q~ (~1 \le n \le 2 \cdot 10^5~, ~1 \le q \le 6 \cdot 10^5~), denoting the number of countries, and the number of events, respectively

The next ~q~ lines, each line describes an event, which takes one of the follow formats:

• 1 u v  – countries ~u~ and ~v~ (~1 \le u, v \le n~, ~u \ne v~) opens a direct flight path to each other. It is guaranteed that there has not been an opened direct flight path between ~u~ and ~v~ before.

• 2 x y  – countries ~x~ and ~y~ (~1 \le x, y \le n~, ~x \ne y~) signs a partnership agreement. It is guaranteed that countries ~x~ and ~y~ have not signed a partnership agreement before.

• 3 k  – country ~k~ (~1 \le k \le n~) makes a technological innovation, and invites all countries that country ~k~ has previously signed partnership agreements with to ~k~ to attend a seminar. It is guaranteed that at least one of this event happens at some point.

Output

For each seminar event (events of type 3), output the number of invited countries attending this event.

Scoring

• Subtask 1 (~80~ points): ~n \leq 10^3~ and ~q \leq 3 \cdot 10^3~.

• Subtask 3 (~125~ points): No additional constraints

The total score for this problem is ~205~.

Sample Input 1

4 8
1 1 3
2 1 4
3 1
1 4 1
2 1 2
3 4
1 2 4
3 1

Sample Output 1

0
1
2

Notes

The first seminar is held by country ~1~. Prior to this event, countries ~1~ and ~4~ has signed a partnership agreement, however country ~1~ only has flights to country ~3~, thereby country ~4~ cannot send delegatees to the event.

The second seminar is held by country ~4~. At this point, country ~1~ now has a direct flight to country ~4~. Note that country ~2~ does not have a partnership agreement with country ~4~, they only signed such agreement with country ~1~.

The last seminar is, again, held by country ~1~. Both countries ~2~ and ~4~ are able to send delegatees to the event. From country ~4~, attendees can take a flight directly to country ~1~. From country ~2~, attendees can fly to country ~4~, then from country ~4~ to country ~1~ to attend the event.