30768번 - Дураки и дороги 다국어

Как известно, в Берляндии ровно две проблемы, и дороги --- одна из них.

Из курса школьной географии вам должно быть знакомо, что в Берляндии ровно $n$ городов и $m$ дорог с двусторонним движением. Некоторые дороги, будем честны, находятся в плачевном состоянии.

Для поддержания качества дорог правительство объявило некоторые из них платными. Каждая платная дорога обслуживается одной из $k$ компаний, которая и обеспечивает своевременный ремонт дороги (она же и взимает плату за проезд по ней).

В Берляндии не только две проблемы, но и две столицы. Они находятся на разных широтах, поэтому одну называют Северной, а другую --- Южной. Споры о том, какая столица главнее, длятся уже много лет, но для компаний важно не кто главнее, а то, что именно между этими двумя городами сосредоточен основной автомобильный трафик.

Берляндская антимонопольная служба заподозрила, что дороги были распределены нечестно, а именно, что существует путь между Северной столицей и Южной, такой что какая-то из компаний не владеет ни одной из дорог этого пути. По мнению представителей службы, это создает нездоровую конкуренцию, и таких ситуаций необходимо избегать, но для начала необходимо выявить все компании, страдающие от подобной несправедливости. Эту нелёгкую задачу антимонопольная служба поручила вам.

Назовем компанию обделённой, если существует какой-нибудь путь между двумя столицами, на котором нет ни одной дороги, обслуживаемой этой компанией. Выведите номера всех обделённых компаний.

В первой строке входных данных записаны три числа $n$, $m$ и $k$ ($2 \leq n, k \leq 100\,000, 1 \leq m \leq 100\,000$) --- количество городов, дорог и компаний соответственно.

Далее следуют $m$ строк, описывающих дороги. В $i$-й из них записаны три целых числа $u_i$, $v_i$ и $c_i$ ($1 \leq u_i, v_i \leq n$, $0 \leq c_i \leq k$) --- номера городов, соединенных $i$-й дорогой, и номер компании, которая эту дорогу обслуживает. При этом $c_i = 0$ означает, что дорога осталась бесплатной и не принадлежит ни одной компании.

В последней строке записаны два числа $a$ и $b$ ($1 \leq a, b \leq n, a \ne b$) --- номера городов, являющихся Северной и Южной столицами соответственно.

Гарантируется, что никакая дорога не соединяет город сам с собой и между каждой парой городов проходит не более одной дороги.

В первой строке выведите количество обделённых компаний.

Во второй строке выведите номера всех обделённых компаний в порядке возрастания.

В первом примере есть путь 1-2-3-4, на котором дороги только первой компании (на рисунке красные) и бесплатные (черные) и нет дорог второй компании, а также путь 1-3-2-4, на котором только дороги второй компании (синие) и бесплатные.

Во втором примере существует всего 2 пути из 1 города в 4: 1-2-4 и 1-3-4. На обоих присутствуют дороги обеих компаний.