Win

Song-i is a baseball fan. She wants her favorite team to finish first, so she predicts the results of the remaining games to see where her team stands.

The league has $M$ games in total. Each game has two teams. There are no draws, so one team always wins and the other loses. The winning team gets 1 point. To take sole first place in the league, a team must have the highest points among all teams, and no other team may have the same points.

Count the number of ways her favorite team can take sole first place. Two orders of playing the games count as one case if the results are the same.

The first line contains three integers $N$, $M$, and $K$, separated by spaces: the number of teams, the number of games, and the team number of Song-i's favorite team. $(2 \leq N \leq 100\,000;$ $1 \leq M \leq 100\,000;$ $1 \leq K \leq N)$

Each of the next $M$ lines describes a game in the form (team 1, team 2, result). Team numbers are integers from $1$ to $N$, and team 1 and team 2 are always different. The result is $0$ if the game has not been played yet, $1$ if team 1 won, and $2$ if team 2 won. At most $20$ games have not been played yet. Her favorite team may not appear in the input.

All numbers in the input are integers.

Print the number of ways her favorite team can take sole first place after all unplayed games are finished.