While vacationing in Egypt, Chef fo

While vacationing in Egypt, Chef found a recipe of an ancient dish. The receipt is a sequence of hieroglyphs written on a magic paper - it survived for thousands of years! The sequence is written on a long scroll. Unfortunately, the scroll is split into pieces, and possibly, some pieces of the scroll are missing. Chef has a total of N pieces, numbered for convenience from 1 to N. He gave the pieces of a tape to his friend who studies hieroglyphs for analysis. Chef was happy to hear that there are some relations between the pieces. Some of the pieces may follow other pieces.
The informations about these relations is given as a list of M pairs (Ai, Bi). Such a pair means that the Aith piece can be immediately followed by the Bith one.
Chef is working on recovering the recipe to prepare this dish for his Egyptian friends. He wants to place all the pieces into lines such that any pair of consecutive pieces (L, R) in a line must be explicitly allowed by one of the M rules described above. In other words, for some i (1 ≤ i ≤ M), (Ai, Bi) = (L, R). It appears that in general, not all the pieces can be placed in a single line while following the rules. So, please help Chef find what is the minimum number of lines required for all the pieces to be placed acoording to the rules.
Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M denoting the number of pieces and number of relations of those N pieces. Next M lines contain two space-separated integers A and B denoting that piece number A can be followed by piece number B, all those pairs are guaraneed to be unique within a test case.

ผลลัพธ์ (ไทย) 1:

ในขณะที่จิตใจในอียิปต์ เชฟพบสูตรของจานเป็นโบราณ ลำดับการ hieroglyphs เขียนบนกระดาษวิเศษเสร็จ - มันรอดชีวิตพัน ๆ ปี ลำดับการเขียนบนเลื่อนยาว อับ เลื่อนแบ่งชิ้น และอาจจะ บางชิ้นเลื่อนหายไป เชฟมีจำนวน N ชิ้น หมายเลขมาจาก 1 การ N. เขาให้ชิ้นส่วนของเทปกับเพื่อนของเขาที่ศึกษา hieroglyphs สำหรับการวิเคราะห์ พ่อครัวมีความสุขที่จะได้ยินว่า มีบางความสัมพันธ์ระหว่างชิ้นส่วน บางชิ้นอาจตามชิ้นอื่น ๆรายละเอียดเกี่ยวกับความสัมพันธ์เหล่านี้ถูกกำหนดเป็นรายการคู่ M (Ai, Bi) คู่ดังกล่าวหมายความ ว่า ชิ้นส่วน Aith สามารถทันทีตาม ด้วย Bith หนึ่งพ่อครัวทำงานในการกู้คืนสูตรเตรียมจานนี้สำหรับเพื่อนของอียิปต์ อยากทำทุกชิ้นเป็นบรรทัดคู่ใด ๆ ต่อชิ้น (L, R) ในบรรทัดต้องชัดเจนสามารถ โดยกฎ M ข้างหนึ่งให้ ในคำอื่น ๆ สำหรับบาง i (1 ≤ฉัน≤ M), (Ai, Bi) = (L, R) ปรากฏว่า โดยทั่วไป ชิ้นส่วนทั้งหมดไม่สามารถวางในบรรทัดเดียวขณะตามกฎ ดังนั้น กรุณาช่วยเชฟค้นหาหมายเลขต่ำสุดของบรรทัดที่จำเป็นสำหรับทุกชิ้นถูกวาง acoording กฎคืออะไรป้อนข้อมูลบรรทัดแรกของข้อมูลป้อนเข้าประกอบด้วยจำนวนเต็มกำหนดเรียกค่าหมายเลขของกรณีทดสอบ T คำอธิบายของ T ทดสอบกรณีดังต่อไปนี้บรรทัดแรกของแต่ละกรณีทดสอบประกอบด้วยสองแบ่งพื้นที่จำนวนเต็ม N และ M กำหนดเรียกค่าจำนวนชิ้นและจำนวนของความสัมพันธ์ของ N ชิ้นเหล่านั้น ต่อ M บรรทัดสองแบ่งพื้นที่จำนวนเต็ม A และ B กำหนดเรียกค่าว่า สามารถตามหมายเลขชิ้นส่วน A ตามจำนวนชิ้น B คู่ที่มีราคา guaraneed จะเป็นเฉพาะในกรณีทดสอบ

ผลลัพธ์ (ไทย) 2:

ขณะที่พักผ่อนหย่อนใจในอียิปต์เชฟพบว่าสูตรของจานโบราณ ใบเสร็จรับเงินเป็นลำดับของกราฟฟิคที่เขียนบนกระดาษมายากล - มันรอดชีวิตมาเป็นพัน ๆ ปี! ลำดับที่เขียนบนเลื่อนยาว แต่น่าเสียดายที่เลื่อนจะแยกออกเป็นชิ้น ๆ และอาจจะเป็นบางชิ้นของเลื่อนหายไป เชฟมีจำนวนชิ้น N, หมายเลขเพื่อความสะดวกสบายจาก 1 ถึงเอ็นเขาให้ชิ้นส่วนของเทปกับเพื่อนของเขาที่ศึกษากราฟฟิคสำหรับการวิเคราะห์ที่ เชฟก็มีความสุขที่จะได้ยินว่ามีความสัมพันธ์บางอย่างระหว่างชิ้น บางชิ้นอาจปฏิบัติตามชิ้นอื่น ๆ .
ข้อมูลเกี่ยวกับความสัมพันธ์เหล่านี้จะได้รับเป็นรายชื่อของคู่ M (อัย Bi) คู่ดังกล่าวหมายความว่าชิ้น Aith สามารถปฏิบัติตามได้ทันทีโดย bith หนึ่ง.
เชฟคือการทำงานในการกู้คืนสูตรเพื่อเตรียมความพร้อมจานนี้สำหรับเพื่อน ๆ ชาวอียิปต์ของเขา เขาต้องการที่จะวางชิ้นส่วนทั้งหมดเข้าเส้นดังกล่าวว่าทั้งคู่ติดต่อกันของชิ้นส่วนใด ๆ (L, R) เป็นเส้นต้องได้รับอนุญาตอย่างชัดเจนโดยหนึ่งในกฎ M อธิบายไว้ข้างต้น ในคำอื่น ๆ สำหรับบางคนที่ฉัน (1 ≤ฉัน≤ M), (อัย Bi) = (L, R) ปรากฏว่าโดยทั่วไปไม่ทุกชิ้นสามารถอยู่ในบรรทัดเดียวในขณะที่ปฏิบัติตามกฎ ดังนั้นโปรดช่วยเชฟหาสิ่งที่เป็นจำนวนขั้นต่ำของสายที่จำเป็นสำหรับชิ้นส่วนทั้งหมดจะอยู่ acoording กฎ.
ป้อนข้อมูลบรรทัดแรกของการป้อนข้อมูลที่มีจำนวนเต็ม T แสดงถึงจำนวนของกรณีการทดสอบ คำอธิบายของ T กรณีทดสอบดังต่อไปนี้. บรรทัดแรกของการทดสอบแต่ละกรณีมีสองจำนวนเต็มพื้นที่แยก n และ M แสดงถึงจำนวนของชิ้นส่วนและจำนวนของความสัมพันธ์ของผู้ที่ยังไม่มีชิ้น M บรรทัดถัดไปมีสองจำนวนเต็มพื้นที่แยก A และ B แสดงถึงจำนวนชิ้นที่สามารถตามด้วยหมายเลขชิ้นส่วน B, คู่ทั้งหมดเหล่านี้จะ guaraneed จะไม่ซ้ำกันภายในกรณีทดสอบ

ผลลัพธ์ (ไทย) 3:

ในขณะที่พักผ่อนหย่อนใจในอียิปต์ เชฟเจอสูตรของจานโบราณ ใบเสร็จเป็นลำดับอักษรที่เขียนบนกระดาษ - มายากลมันรอดนับพันปี ! ลําดับที่เขียนไว้บนเลื่อนยาว ขออภัย คัมภีร์แบ่งออกเป็นชิ้น และบางชิ้นอาจจะเลื่อนหายไป เชฟมีทั้งหมด n ชิ้น หมายเลขเพื่อความสะดวกจาก 1 ถึง Nเขาให้ชิ้นส่วนของเทปกับเพื่อนที่เรียนอักษรสำหรับการวิเคราะห์ เชฟมีความสุขที่จะได้ยินว่ามีความสัมพันธ์ระหว่างชิ้น บางชิ้นอาจตามชิ้นอื่น ๆ ข้อมูลเกี่ยวกับ
ความสัมพันธ์เหล่านี้ให้รายการของ M คู่ ( ไอ บี ) เช่นคู่หมายความว่า aith ชิ้นสามารถทันทีตามด้วย bith
1เชฟกำลังฟื้นตัวสูตรเพื่อเตรียมอาหารจานนี้สำหรับเพื่อนๆชาวอียิปต์ของเขา เขาต้องการที่จะวางชิ้นทั้งหมดลงในบรรทัดเช่นคู่ของชิ้นติดต่อกัน ( L , R ) ในบรรทัดต้องได้รับอนุญาตอย่างชัดเจนโดยหนึ่งของ M กฎที่อธิบายข้างต้น ในคำอื่น ๆสำหรับผม ( 1 ≤ผม≤ M ) ( ไอ บี ) = ( L , R ) ปรากฏว่า ในทั่วไปไม่ทุกชิ้นสามารถวางในบรรทัดเดียว ขณะที่ตามกฎ ดังนั้น ได้โปรดช่วยเชฟหาสิ่งที่เป็นจำนวนขั้นต่ำของบรรทัดที่จำเป็นสำหรับทุกชิ้นจะถูกวางไว้ acoording กฏ

.
ข้อมูลบรรทัดแรกของข้อมูลประกอบด้วยจำนวนเต็มไม่แสดงถึงจำนวนของกรณีทดสอบ รายละเอียดของกรณีทดสอบ T
1บรรทัดแรกของแต่ละกรณีทดสอบมีพื้นที่สองแยกจำนวนเต็ม n และ m แสดงถึงจำนวนชิ้น และจำนวนของความสัมพันธ์ของ n ชิ้น สาย M ต่อไปประกอบด้วยพื้นที่สองแยกจำนวนเต็ม a และ b denoting ที่จำนวนสามารถตามด้วยชิ้นส่วนของจำนวนทั้งหมดที่เป็นคู่ guaraneed ต้องไม่ซ้ำกันภายในกรณีทดสอบ .