Most Influential User

You are given a social media platform with N users (numbered from 1 to N) and M interactions between them. Each interaction is represented as a directed pair \( (u, v) \), meaning that user \( u \) has interacted with user \( v \).

The goal is to determine the most influential user based on the number of unique users that have interacted with them. In other words, for each test case, you have to compute for every user \( v \) the number of distinct users \( u \) that have interacted with \( v \). The answer is the user with the highest count. In case of a tie, choose the user with the smallest user ID. Note that if there are no interactions, the answer should be 1 (since it is the smallest user ID by default).

Formally, for each test case, let \( S(v) \) be the set of users that have interacted with user \( v \). Find \( v \) such that \(|S(v)|\) is maximized, and if multiple users share the same maximum value, output the one with lowest ID.

inputFormat

The input begins with an integer T, representing the number of test cases. For each test case, the first line contains two integers N and M, where N is the number of users and M is the number of interactions. This is followed by M lines, each containing two integers u and v, denoting an interaction from user u to user v.

outputFormat

For each test case, output a single line with the user ID of the most influential user.## sample

1
5 4
1 3
2 3
2 4
1 5

3