31862번 - 승리하라

문제

야구팬인 송이는 응원하는 팀이 1위를 했으면 좋겠다는 마음에 남은 경기 결과를 예측하여 현재 본인 팀의 상황을 파악해 보려고 한다.

리그에 게임이 총 $M$개 존재한다. 게임은 두 팀이 참여하고 경기는 무승부가 존재하지 않아 한 팀이 무조건 승리하고 다른 팀이 패배할 때까지 진행된다. 여기에서 이기는 팀이 승점 1ドル$점을 가져가게 된다. 리그에서 단독 1위를 하려면 모든 팀 중에 승점이 가장 높아야 하고, 같은 승점을 가진 다른 팀이 있으면 안 된다.

송이의 응원팀이 단독 1위를 할 수 있는 경우의 수를 구하여라. 이때 경기를 진행하는 순서가 다르더라도 경기 결과가 같으면 하나의 경우로 취급한다.

입력

팀의 수 $N$과 경기의 수 $M$과 응원하는 팀번호 $K$가 첫째 줄에 공백으로 구분되어 주어진다. $(2 \leq N \leq 100,000円;$ 1ドル \leq M \leq 100,000円;$ 1ドル \leq K \leq N)$

다음 $M$개의 줄에 (팀 번호 1, 팀 번호 2, 경기 결과) 의 형태로 경기 내용이 주어진다. 팀 번호는 1ドル$ 이상 $N$ 이하의 정수로 팀 번호 1과 팀 번호 2는 서로 다름이 보장된다. 경기 결과는 0ドル,ドル 1ドル,ドル 2ドル$ 중 하나로 0ドル$인 경우 경기가 아직 진행되지 않은 경우이고 1ドル$의 경우 팀 번호 1의 팀이 이긴 경우, 2ドル$의 경우 팀 번호 2의 팀이 이긴 경우를 의미한다. 아직 진행되지 않은 경기는 최대 20ドル$경기이며 응원하는 팀이 입력에 나오지 않는 경우도 있을 수 있다.

입력으로 주어지는 수는 모두 정수이다.

출력

아직 진행되지 않은 경기가 모두 진행되었을 때 응원하는 팀이 단독 1위가 되는 경우의 수를 출력한다.

제한

힌트