Xorfy's circuit

0

0 votes
Problem

Xorfy wanted to put a light bulb on the top of her Christmas tree which could be lighted from below. She had received as a present a bulb which lighted only on receiving a logical value of 1. She also had switches which gave a logical output of 1 and 0, in on and off state respectively. So, she made a circuit in the following way:

She took a directed acyclic multigraph with N nodes and M edges. The nodes were numbered from 1 to N. At each node, she put a XOR gate (which could have any number of inputs). She connected switches as inputs to the XOR gates at all the nodes with indegree 0. Then for every edge going from node U to node V in the graph, she wired the output of the XOR gate at U to an input of the XOR gate at V. Finally, at one of the nodes with outdegree 0, she connected a light bulb to the output of the XOR gate at that node. Note that a XOR gate with a single input behaves as simple wire.

But she was not happy with this circuit as she soon discovered that some switches in her circuit did not affect the light bulb at all. She wants to remove these switches. Can you help her by computing the number of such switches?

INPUT

The first line contains the number of testcases, T.

The description of T testcases follow. For each testcase:

The first line contains 3 integers N, M and K, the number of nodes, the number of edges and the node with the bulb respectively.

M lines follow, each containing 2 integers U and V, denoting an edge from node U to node V.

OUTPUT

For each testcase, output in a single line the number of switches Xorfy should remove.

CONSTRAINTS

1 <= N <= 1,00,000

The sum of N over all testcases <= 10,00,000

0 <= M <= 1,00,000

The sum of M over all testcases <= 10,00,000

Subtask: 5 out of 20 input files have sum of N over all testcases <= 1,000 and sum of M over all testcases <= 1,000.

1 <= K <= N

1 <= U, V <= N and U != V for every edge U to V.

The graph described on the input is a valid directed acyclic multigraph.

TIME LIMIT: 1 second

AUTHOR: Rishabh Ranjan
TESTER: Navneel Singhal

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Switch at node 5 can be removed as it does not affect the light bulb.

Editor Image

?