Занятие 20

Исландия – страна, расположенная на множестве мелких островков. Прошло уже много времени, с того момента, когда был построен первый мост. Сейчас это государство полностью соединено мостами, и с любого острова можно попасть на любой другой, не пользуясь лодкой. Недавно жители решили добавить к уже большому списку праздников еще один – День Объединения. Как вы, наверное, уже догадываетесь, так они решили назвать тот день, в который жители перестали нуждаться в лодках для перемещения между любыми двумя островами. К сожалению, было построено очень много мостов, и разобраться, когда же настал этот день, оказалось не совсем просто.

Жители Исландии будут вам очень благодарны, если вы напишете программу, которая определит по датам постройки мостов, когда же наступил этот знаменательный день. Итак, надо определить тот день, в который все острова оказались соединенными (пусть даже через другие острова) мостами.

В первой строке ввода содержатся два числа `N` и `K` – количество островов и мостов соответственно `(2\ ≤\ N\ ≤\ 1000,\ 1\ ≤\ K\ ≤\ 10000)`. В последующих `K` строках вам будет дана информация о мостах в следующем виде a b date, где date – дата в формате dd/mm/yyyy, а числа a и b – номера островов, которые соединил построенный мост. Записи упорядочены по времени, последний построенный мост – в конце файла. Гарантируется, что после постройки последнего моста в Исландии с любого острова можно попасть на любой другой, пользуясь только мостами (возможно несколькими).

Вывести единственную дату, записанную в том же формате, что и во входном файле, соответствующую тому дню, когда жители Исландии смогли ходить друг в другу в гости пешком.

5 10
1 3 04/10/1607
5 4 25/05/1665
2 5 13/12/1746
5 4 06/06/1799
2 4 01/04/1815
3 1 22/11/1836
3 5 17/08/1855
4 1 15/11/1897
5 1 21/04/1931
2 3 14/05/1967

17/08/1855