Winner Prediction

A tournament consisting of $n$ participants is currently taking place. The players are numbered from $1$ to $n$. Every match is between two participants, and there are no draws. The participant who wins the most matches wins the entire tournament; if there are multiple participants tied at the first place, all of them win the tournament.

At the current state, some matches have ended, and others are yet to start. You are given the results of all ended matches. Write a program to determine whether it is possible for player $1$ to win the tournament.

You are given $T$ independent test cases. Solve each of them.

The first line of input consists of a single integer $T(1\leq T\leq 100)$, indicating the number of test cases. Then $T$ test cases follow.

Each of the $T$ test cases consists of multiple lines.

The first line contains three integers $n,m_1,m_2(1\leq n\leq 500,1\leq m_1,m_2 \leq 1000)$, indicating the number of participants, the number of ended matches and the number of upcoming matches.

Each of the next $m_1$ lines contains three space-separated integers $x,y,z(1\leq x,y \leq n,x \neq y,0\leq z \leq 1)$, indicating an ended match between player $x$ and player $y$ , $z = 1$ means player $x$ won the match and $z=0$ means player $y$ won the match.

Each of the next $m_2$ lines contains two space-separated integers $x,y(1 \leq x,y \leq n,x \neq y)$, indicating an upcoming match between player $x$ and player $y$.

For each test case, if it is possible of player $1$ to win the tournament, print a line $\texttt{YES}$; otherwise print a line $\texttt{NO}$.

2
4 2 1
2 3 1
3 2 1
1 4
4 2 2
2 3 1
2 4 1
1 2
3 4

YES
NO

2022“杭电杯”中国大学生算法设计超级联赛（10）