Дураки и дороги

문제

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

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

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

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

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

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

입력

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

Далее следуют $mm$ строк, описывающих дороги. В $ii$-й из них записаны три целых числа $u_{i}u\_i$, $v_{i}v\_i$ и $c_{i}c\_i$ ($1\le u_i,v_i\le n1\; \backslash leq\; u\_i,\; v\_i\; \backslash leq\; n$, $0\le c_i\le k0\; \backslash leq\; c\_i\; \backslash leq\; k$) --- номера городов, соединенных $ii$-й дорогой, и номер компании, которая эту дорогу обслуживает. При этом $c_i=0c\_i\; =\; 0$ означает, что дорога осталась бесплатной и не принадлежит ни одной компании.

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

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

출력

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

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

힌트

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

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

[이미지 1]