Brightline - 미래로 돌아가기

UCF 프로그래밍 팀 코치들 중 많은 사람이 나이가 들어 젊음을 되찾을 방법을 찾고 있다. 도시에 새 열차 Brightline이 들어왔다. 열차를 몇 번 타면 젊어질 수 있다는 소문이 있다.

Brightline에는 파란색 노선과 빨간색 노선, 두 종류의 열차가 있다. 파란색 노선에서는 승객이 정해진 시간만큼 나이를 먹는다. 빨간색 노선에서는 승객이 정해진 시간만큼 과거로 돌아간다.

각 노선에는 방향이 있다. 노선은 출발 도시와 도착 도시를 잇고, 빨간색 또는 파란색으로 구분되며, 양의 정수가 주어진다. 이 값은 그 노선을 탈 때 승객이 나이를 먹는 분(파란색) 또는 과거로 돌아가는 분(빨간색)이다. 도시에 도착하면 그 도시에서 출발하는 열차를 바로 탈 수 있다.

이 시스템에서는 과거로 무한히 돌아갈 수 없다. 어떤 도시에서 출발해 같은 도시로 돌아왔을 때 출발할 때보다 젊어져 있는 경로는 존재하지 않는다.

코치들은 모두 오를란도(1번 도시)에 산다. 모든 Brightline 노선이 주어질 때, 1번 도시에서 출발해 출발할 때보다 젊은 상태로 도착할 수 있는 모든 도착 도시를 구하라.

첫 줄에 두 정수 $n$ ($1 \le n \le 5 \times 10^3$)과 $m$ ($1 \le m \le 10^4$)이 주어진다. 도시는 1부터 $n$까지 번호가 매겨지며, 1번 도시가 오를란도이다.

다음 $m$개의 줄에는 각각 한 노선에 대한 네 가지 값이 주어진다.

• $s$ ($1 \le s \le n$): 노선의 출발 도시
• $e$ ($1 \le e \le n$, $s \ne e$): 노선의 도착 도시
• $t$ ($t =$ 'b' 또는 'r'): 파란색 노선이면 'b', 빨간색 노선이면 'r'
• $a$ ($1 \le a \le 10000$): 이 노선을 탈 때 나이를 먹는(파란색) 또는 과거로 돌아가는(빨간색) 분 단위 시간

1번 도시에서 출발해 출발할 때보다 젊은 상태로 도착할 수 있는 도시를 모두 번호의 오름차순으로 출력한다.