Masala F

Robolandiya - go'zal diyor. U N ta shaharni o'z ichiga oladi, va shaharlar 1 dan N gacha raqamlangan.

Robolandiya mamlakatida turli shaharlarni bog'laydigan M ta ikki tomonlama yo'l mavjud.

Robolandiya qo'riqchilari o'z prezidentini juda kuchli qo'riqlashadi. Bundan tashqari prezident xizmat safari bilan qaysi shaharga borishidan qat'iy nazar shu shaharga bog'langan barcha yo'llarni yopishadi ham.

Robolandiya fuqarolarini mamlakat bo'ylab sayohat qilishlari uchun tashkil etilgan sayyohlik agentligi o'z sayohatlarini avtobuslarda amalgan oshirganligi sababli ba'zi $u \neq v (1 \le u, v \le n)$ juftliklar uchun u-shaharda istiqomat qiladigan fuqarolarni v-shaharga sayohatga eta olishmaydi.

Sayyohlik agentligi har bir $i$ - shahar uchun, agar mamlakat prezidenti xizmat safari bilan $i$-shaharga kelgan bo'lsa jami nechta  $u \neq v (1 \le u, v \le n)$ juftliklar uchun u-shaharda istiqomat qiladigan fuqarolarni v-shaharga sayohatga eta olmasligini aniqlamoqchi.

Siz yuqori malakali dasturchi sifatida sayyohlik agentligiga yordam bering!.

Birinchi qatorda N va M, shaharlar va ularni bog'lab turuvchi ikki tomonlama yo'llar soni kiritiladi.

Keyingi M ta qatorning har birida ikkitadan butun son - har bir yo'l bog'lab turadigan ikki shaharning tartib raqami kiritiladi.

$1 \le N \le 10^5$

$1 \le M \le 5*10^5$

$1 \le i \le N$ oralig'idagi har bir $i$ uchun alohida qatorda, Robolandiya prezidenti xizmat safari bilan $i$- shaharda bo'lganida sayyohlik agentligi jami nechta  $u \neq v (1 \le u, v \le n)$ juftliklar uchun u-shaharda istiqomat qiladigan fuqarolarni v-shaharga sayohatga eta olmasligini chop eting.