해킹

악명 높은 해커가 네트워크의 한 컴퓨터를 해킹했다. 컴퓨터 a가 b에 의존하면 b가 감염된 뒤 s초 후 a도 감염된다. b가 a에 의존하지 않으면 a가 감염되어도 b는 안전하다.

해킹된 컴퓨터 번호와 의존성이 주어질 때, 감염되는 컴퓨터 수와 마지막 감염까지 걸리는 시간을 구하라.

첫 줄에 테스트케이스 수 $T$가 주어진다 ($T \le 100$).

각 테스트케이스마다 $n$, $d$, $c$가 주어지고 ($1 \le n \le 10000$, $1 \le d \le 100000$, $1 \le c \le n$), 이어서 $d$줄에 $a$, $b$, $s$가 주어진다. a가 b에 의존하며 b가 감염되면 s초 후 a가 감염된다.

각 테스트케이스마다 감염되는 컴퓨터 수와 마지막 감염 시각을 공백으로 구분해 출력한다.