На факултету постоје зависности између испита који се полажу. На пример, да би се полагао испит “Програмирање 2”, претходно је неопходно да је положен испит “Програмирање 1”. Зависности су задате матрицом логичких вредности која представља једну релацију. Напиши програм који проверава да ли су испуњени следећи услови:

• релација је антирефлексивна тј. не постоји ни један предмет који зависи сам од себе,
• релација је антисиметрична тј. не постоје два предмета који међусобно зависе један од другог,
• релација је транзитивна тј. ако један предмет зависи од другог, а тај други зависи од трећег, онда је неопходно да и први предмет зависи од трећег.

Улаз

Са стандардног улаза се уноси број предмета \(n\) (\(5 \leq n \leq 10\)), а затим матрица димензије \(n \times n\) која садржи само нуле и јединице - јединица у врсти \(v\) и колони \(k\) означава да предмет са редним бројем \(v\) зависи од предмета са редним бројем \(k\).

Излаз

На стандардни излаз исписати DA ако матрица испуњава све задате услове тј. NE ако нарушава било који од њих.

Пример

Улаз

6
0 0 0 0 0 0
1 0 1 0 1 0
1 0 0 0 1 0
1 1 1 0 1 0
1 0 0 0 0 0
0 0 0 0 0 0

Излаз

DA