Məlumatçılar
Macondo Əks-kəşfiyyat Agentliyi, qısaca MƏKA, informantlarının keyfiyyətini sadə, lakin yüksək dəqiqliklə qiymətləndirən bir prosedurla sınamaq istəyir. Bu prosedur informantlar qrupunun nə dərəcədə etibarlı olduğunu qiymətləndirir.
MƏKA informantlar qrupunun etibarlılığını onların arasındakı etibarlılığı sorğulamaqla müəyyən edir: informantlar digər informantlar, hətta özləri haqqında xüsusi fikirlərini bildirirlər. Sorğunun nəticəsi olaraq, MƏKA "X deyir ki, Y etibarlıdır" və ya "X deyir ki, Y etibarlı deyil" formasında bir sıra bəyanatlar toplayır. Əgər X etibarlı olarsa, MƏKA onun dediklərinin doğru olduğunu qəbul edir. Əks halda, əgər X etibarlı deyilsə, onun fikirləri doğru və ya yanlış ola bilər. Sonda, MƏKA sorğunun cavablarına əsasən etibarlı ola biləcək maksimum informant sayını müəyyən edərək vəziyyəti qiymətləndirir.
Məsələn, dörd informantın A, B, C və D olduğunu və aşağıdakı sorğu cavablarının olduğunu fərz edək: "A deyir ki, B etibarlıdır, amma D etibarlı deyil", "B deyir ki, C etibarlı deyil" və "C deyir ki, A və D etibarlıdır". Bu halda, ən çox iki informant etibarlı ola bilər.
Sizin vəzifəniz MƏKA-ya kömək edərək, sorğunun nəticələrinə əsasən etibarlı ola biləcək maksimum informant sayını hesablayan səmərəli bir proqram yazmaqdır.
Giriş verilənləri
Problemin girişi bir neçə haldan ibarətdir. Hər bir test halı boşluqlarla ayrılmış iki qeyri-mənfi tam ədəd, i (0 < i ≤ 20) və a (0 ≤ a ≤ 800) ilə başlayan bir sətirdən ibarətdir. i informantların sayını, a isə etibarlılıq sorğusundakı cavabların sayını göstərir. Sonra, a sətir gəlir, hər biri boşluqlarla ayrılmış iki tam ədəd x və y (1 ≤ x ≤ i, 1 ≤ |y| ≤ i). Əgər y müsbətdirsə, giriş sətri "informant x deyir ki, informant y etibarlıdır" deməkdir. Əgər y mənfidirsə, onda sətr "informant x deyir ki, informant y etibarlı deyil" deməkdir. Girişin sonu iki 0 dəyəri olan bir sətirlə göstərilir (nəzərə alınmamalı olan süni hal).
Çıxış verilənləri
Hər bir giriş halı üçün, sorğunun cavablarına əsasən etibarlı ola biləcək maksimum informant sayını bir sətirdə çıxış edin.