베시는 최근 새로운 에라 투어에서 그의 최애 팝 아티스트 엘시 스위프트가 공연을 한다는 것을 알게 되었습니다! 유감스럽게도 티켓이 빠르게 매진되어, 베시는 다른 도시로 비행하여 콘서트에 참석할 생각입니다. 에라 투어는 N(2≤N≤750)개의 도시에서 진행되며, 각 도시 쌍 (i,j)에 대해 i<j이면 i에서 j로의 직접 비행이 있을 수도 없을 수도 있습니다.

도시 a에서 도시 b로의 비행 경로(a<b)는 k≥2인 도시 시퀀스 a=c1<c2<⋯<ck=b로 정의됩니다. 여기서 1≤i<k인 모든 i에 대해 도시 ci에서 도시 ci+1로의 직접 비행이 있어야 합니다. i<j인 모든 도시 쌍 (i,j)에 대해 그들 사이의 비행 경로 수의 홀짝 여부가 주어집니다(0은 짝수, 1은 홀수).

여행 일정을 계획하다가 베시는 살짝 머리가 복잡해져서 이제 도시 쌍 간에 직접 비행이 몇 개인지 궁금해졌습니다. 답은 유일하게 결정될 수 있다고 합니다.

Bessie recently discovered that her favorite pop artist, Elsie Swift, is performing in her new Eras Tour! Unfortunately, tickets are selling out fast, so Bessie is thinking of flying to another city to attend the concert. The Eras tour is happening in N (2≤N≤750) cities labeled 1…N, and for each pair of cities (i,j) with i<j there either exists a single direct flight from i to j or not.

A flight route from city a to city b (a<b) is a sequence of k≥2 cities a=c1<c2<⋯<ck=b such that for each 1≤i<k, there is a direct flight from city ci to city ci+1. For every pair of cities (i,j) with i<j, you are given the parity of the number of flight routes between them (0 for even, 1 for odd).

While planning her travel itinerary, Bessie got distracted and now wants to know how many pairs of cities have direct flights between them. It can be shown that the answer is uniquely determined.

#6096 upload 7 done 1 how_to_reg 1

비행 경로(Flight Routes) timer 1s memory 512MB

#6096

비행 경로(Flight Routes) 1s 512MB