Сначала вводятся числа \(N\) - количество вершин \(N\)-угольника (3 <= \(N\) <= 1000) и \(M\) - количество диагоналей, проведенных Васей. Далее на вход программы поступают \(M\) пар чисел, задающих диагонали (каждая диагональ задается парой номеров вершин, которые она соединяет). Гарантируется, что каждая пара чисел задает диагональ (то есть две вершины различны и не являются соседними), а также что никакие две пары не задают одну и ту же диагональ. Никакие две диагонали не пересекаются внутри \(N\)-угольника. Вершины \(N\)-угольника нумеруются числами от 1 до \(N\).

В первой строке входных данных содержится число \(N\) (1 <= \(N\) <= 100000). Во второй строке задается последовательность из \(N\) больших латинских букв (буквы записаны без пробелов).