— А сами драконы именно так поступают, когда хотят найти себе пару? — спросила Принцесса.

— Драконы живут по одному. Они появляются, когда их придумывают люди. И исчезают, когда о них забывают, — ответил Дракон.

Дракон рассказал Принцессе, что когда кто-то придумывает нового дракона, то в Долине Замков появляется новый замок, в котором и проживает вновь придуманный дракон. А когда дракона долго никто не тревожит, он впадает в спячку.

Иногда в Долине Замков идёт необычный дождь: на небе ни облачка, ярко светит солнце, и только крупные частые капли стучат по крыше замка, в котором уснул дракон. А когда дождь заканчивается, на месте этого замка окажется лужайка с полевыми цветами. Более того, ручейки дождевой воды бегут по дорожкам, что ведут от этого замка. Если дорожка приводит к замку с бодрствующим драконом, то ручеёк останавливается. Если же на пути ручейка встречается замок с уснувшим драконом, замок тоже превратится в лужайку, а ручеёк побежит дальше.

И хотя драконы — всего лишь выдумка, они сочувствуют спящим драконам. Они научились предугадывать такие дожди, но узнавать заранее, на какой именно замок прольётся такой дождь, они не умеют. Вместе с тем, они хотят добиться того, чтобы количество лужаек после дождя, на какой бы замок он ни пролился, было как можно меньшим. Совместными усилиями они могут успеть разбудить до дождя ровно одного дракона из впавших в спячку. Теперь они хотели бы узнать, дракона в каком замке им следует разбудить. Ваша задача — определить это.

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