信息学集训队作业biutask.pdfVIP

Task:BIU

Offices

StageI.Day1.Sourcefilebiu.*2006.10.23

Availablememory:64MB.

Bytelisamobiletelephonypotentate.Eachemployeehasbeenissuedacompanyphone,thememoryof

whichholdsthenumbersofsomeofhisco-workers(allofthemhavehisnumberintheirphonesaswell).

Duetodynamicgrowthoftheiroperationstheboardofdirectorsintendstomovecompanyheadquatersto

newofficebuildings.Ithasbeendecided-inordertoboostworkefficiency-thateverypairofemployees

workingindifferentbuildingsshouldknow(reciprocally)eachothersphonenumberi.e.thememoryoftheir

companyphoneoughttoholdnecessaryphonenumbers.

Simultaneously,theboardhavedecidedtorentasmanyofficebuildingsaspossibletoensuregoodwork-

ingconditions.HelptheboardofByteltoplanthenumberofofficebuildingsandtheirsizeinaccordance

withtheaforementionedrequirements.

Task

Writeaprogrammewhich:

•readsthedescriptionofemployees’phonenumberlistsfromthestandardinput

•calculatesthealnumberofofficebuildingsandtheirsizes,satisfyingboard’sconditions

•writestheoutcometothestandardoutput.

Input

Thefirstlineofthestandardinputconsistsoftwointegers:nandm(2≤n≤100000,1≤m≤2000000),

separatedbysinglespaces,denotingthenumberofBytelemployeesandthenumberofpairsofemployees

whohavetheirnumbersincompanyphones,respectively.Theemployeesarenumberedfrom1ton.

Eachofthefollowingmlinescontainsasinglepairofintegersaib(1≤ab≤nfor1≤i≤m),

iiii

separatedbyasinglespace,denotingthatemployeesaandbhavetheirnumbers(reciprocally)incompanyii

phones’memory.Eachpairofintegersdenotingapairofemployeesshalloccuronceatthemostinthe

standardinput.

Output

Thefirstlineofthestandardoutputshouldcontainasingleinteger:thealnumberofofficebuildings

thatBytelshouldrent.Thesecondshouldcontainanon-decreasingsequenceofpositiveintegers,separated

bysingespaces,denotingthesizesoftheofficebuil