İnsayder məlumatı
Yan reytinq agentliyində işləyir və burada ən yaxşı universitetlərin reytinqləri dərc olunur. İren isə qarşıdakı reytinq haqqında qalmaqallı bir məqalə yazmağı planlaşdıran jurnalistdir.
Sosial mühəndislik metodlarından istifadə edərək (detallara girməyək) İren Yan-dan bəzi daxili məlumatlar əldə edib.
Xüsusilə, İren bir neçə üçlük (a[i], b[i], c[i]) əldə edib, bu da o deməkdir ki, qarşıdakı reytinqdə b[i] universiteti a[i] və c[i] universitetləri arasında yerləşir. Yəni ya a[i] b[i]-dən əvvəl, b[i] isə c[i]-dən əvvəl gəlir, ya da əksinə. Yan tərəfindən verilən bütün üçlüklər ziddiyyətsizdir - yəni, real reytinq onların hamısını təmin edir.
İren gələcək məqalənin ilk eskizini hazırlamaq üçün real reytinqə yaxın bir şey görməlidir. O, sizdən İrenə məlum olan üçlüklərin ən azı yarısını təmin edən bir reytinq təklifi tapmağı xahiş edir.
Giriş məlumatları
Birinci sətirdə n və m tam ədədləri (3 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5) - reytinqə daxil olan universitetlərin sayı və Yan tərəfindən İrenə verilən üçlüklərin sayı qeyd olunub.
Növbəti m sətirin hər biri üç fərqli tam ədəd (1 ≤ a[i], b[i], c[i] ≤ n) - üçlüyü təşkil edən universitetlərdən ibarətdir.
Çıxış məlumatları
Birinci universitetdən sonuncuya qədər təklif olunan reytinqi çıxarın. Təklif olunan reytinq ən azı m / 2 üçlüyü təmin etməlidir. Əgər belə təkliflər bir neçədirsə, onlardan hər hansı birini çıxarın.
Nümunə
Nümunədə ilk iki üçlük təmin olunur, lakin sonuncu təmin olunmur. Beləliklə, ən azı bütün üçlüklərin yarısı təmin edilir.