CHUNK1 - Help Robin!!

Ra's al Ghul has attacked Gotham city and wants to kill Batman.

Now you, being Robin, want to help Batman by killing Ra's al Ghul and his army.

Ra's al Ghul has army of soldiers commanded by certain chiefs amongst them. The soldiers are motivated by them and are geared up to follow their instructions on one say.

You have to identify chief soldiers and use them to misdirect maximum number of soldiers. This will reduce the chance of Ra's al Ghul to kill Batman.

Chief soldiers are those who are followed by the maximum number of soldiers.

Once, identified you can play trick (magic) on them and misdirect soldiers following them.

You are given two integers N (denoting number of soldiers) and M (number of relation between 'N' soldiers).

Further, M lines contains two integers l1 and l2 meaning soldier l1 follows soldier l2.

Constraints

1 <= T <= 100

1 <= N <= 9999

1 <= M <= 100000

1 <= l1, l2 <= N

Input

The first line of the input contains a single integer T denoting number of test cases. Description of each test case are as follows:

First line contain integers N (denoting the number of soldiers) and M (number of pairs).

Further, M lines contains two integers l1 and l2, meaning soldier l1 follows soldier l2.

Output

Print the chief soldiers in ascending order.

Example

Input:
1
5 4
1 5
1 2
3 1
4 1

Output:
2 5

Explanation:

  • 1st soldier follows 5th soldier
  • 1st soldier follows 2nd soldier
  • 3rd soldier follows 1st soldier
  • 4th soldier follows 1st soldier
  • Number of soldiers following 4 = 0
  • Number of soldiers following 3 = 0
  • Number of soldiers following 1 = 2 (4th and 3rd soldiers)
  • Number of soldiers following 2 = 3 (4th, 3rd and 1st soldiers)
  • Number of soldiers following 5 = 3 (4th, 3rd and 1st soldiers)

Answer is soldiers 2 and 5.

Contributed by: Paras Jain


Added by:chunky_2808
Date:2018-08-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:None

hide comments
2018-12-22 19:08:27
any idea how to deal the cases having cycles!!!
algo fails after test 10

Last edit: 2018-12-22 19:10:19
2018-09-14 16:52:02
we can solve this my hashmap
2018-08-02 20:24:27
I don't know what I am missing! I am simply creating a DAG and checking size of adjacency list. If size of that element is zero I am including it in the answer. Please help @nadstratosfer if my approach is wrong.

Last edit: 2018-08-02 20:41:48
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.