C. Clubhouse Celebrity
time limit per test
3 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Catherine is an intern of Clubhouse, the voice-only social media. There are $$$n$$$ users in Clubhouse, numbered from $$$1$$$ to $$$n$$$. Catherine wants to develop a new feature to find out the celebrity in a chatroom with $$$m$$$ people. A person among these $$$m$$$ people is called a celebrity if and only if he/she satisfies all the following conditions:

  • He/She is in the chatroom.
  • He/She is followed by all the others in the chatroom.
  • He/She is followed by at least one person in the chatroom.
  • He/She does not follow anyone in the chatroom.
A celebrity can make his/her profile picture invisible in the chatroom to avoid too much attention. Please help Catherine to find out the celebrity or determine if he/she exists.
Input

The first line contains two integers $$$n$$$, $$$m$$$. $$$n$$$ ($$$1 \le n \le 2021$$$) is the number of all users in Clubhouse. The users in clubhouse are numbered from $$$1$$$ to $$$n$$$. $$$m$$$ ($$$1 \le m \le n$$$) is the number of users in a chatroom.

In the following $$$2m$$$ lines, each $$$2$$$ lines contains the following information of those users in the chatroom. The first line of each following information contains two integers $$$u$$$, $$$t$$$. $$$u$$$ ($$$1 \le u \le n$$$) is the ID number of one of the users in the chatroom. $$$t$$$ ($$$0 \le t \le n - 1$$$) is the number of users that this user follows. The second line contains $$$t$$$ integers $$$a_1, a_2, \ldots, a_t \, (0 \leq a_1, a_2, \ldots, a_t \leq n)$$$ if $$$t \geq 1$$$, which is a list of ID numbers of the users that this user follows. However, if $$$t = 0$$$, which means the person in the chatroom does not follow anyone, the "list" in the second line will be 0 (see the second example, the second person in the chatroom). It is guaranteed that a user will not follow himself/herself.

Output

If the celebrity exists, output the user's ID of the celebrity. Otherwise, output -1.

Examples
Input
7 4
1 4
2 3 4 7
2 1
3
3 3
5 6 7
4 2
1 3
Output
3
Input
3 3
1 2
2 3
2 0
0
3 1
1
Output
-1
Note

In the first example, user $$$1$$$ follows $$$4$$$ people, who are user $$$2$$$, $$$3$$$, $$$4$$$, and $$$7$$$; user $$$2$$$ follows $$$1$$$ person, who is user $$$3$$$; user $$$3$$$ follows $$$3$$$ people, who are user $$$5$$$, $$$6$$$, and $$$7$$$; user $$$4$$$ follows $$$2$$$ people, who are user $$$1$$$ and $$$3$$$. As user $$$3$$$ is in the chatroom followed by all the others in the chatroom and does not follow any user in the chatroom, he/she is the celebrity.