Dropping Directions

A rival sports club in your city has pulled several nasty stunts on you, and now it is your turn. You found out what they are planning. They blindfold their members, drive them to a city none of them knows, drop them anywhere in it, and tell them to find one specific place, the goal. The members then wander around the city looking for it.

You decide to ruin that game. The first member to reach the goal wins a prize, so the participants will use anything that helps them. If official looking signposts are already standing in the city, they will follow them. Place the signposts so that a participant dropped anywhere reaches the goal by following signs, and the wandering is over.

Signposts are expensive and police officers notice them, so you want as few of them as possible. A long detour does not bother you. The participants do not know the city anyway.

Every intersection in this city is a crossing of four roads, which makes the participants easy to predict.

• A participant who enters an intersection leaves it on the opposite road.
• A participant who reaches an intersection that has a signpost walks in the one direction the sign points, whether dropped there or passing through.
• A participant dropped at an intersection without a signpost picks one of the four roads arbitrarily and walks off.

One signpost points along exactly one of the four roads at its intersection. No participant is ever dropped at the goal.

Find the smallest number of signposts that brings every participant to the goal, no matter which intersection they are dropped at and which road they pick first.

The first line has the number of test cases $T$. ($1 \le T \le 100$)

Each test case has this form.

• One line with two space separated integers $n$ and $g$, the number of intersections and the goal. ($5 \le n \le 100000$, $1 \le g \le n$)
• Then $n$ lines. Line $i$ has four integers $a$, $b$, $c$, $d$. ($1 \le a, b, c, d \le n$) A participant who enters intersection $i$ from the side of intersection $a$ leaves toward intersection $c$, and one who enters from the side of $c$ leaves toward $a$. In the same way, one who enters from the side of $b$ leaves toward $d$, and one who enters from the side of $d$ leaves toward $b$.

Each intersection is connected to four different intersections. Roads are two way, so if $j$ appears in the list of intersection $i$, then $i$ appears in the list of intersection $j$. Every intersection of the city can be reached from every other along the roads.

For each test case, print one line with the smallest number of signposts needed.