L16. M-Coloring Problem | Backtracking

Подписаться 664 тыс.

Просмотров 200 тыс.

50% 1

Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------------------------------- Pre-Requisites: Recursion Playlist Videos, Representation in Graph Videos
---------------------------------------------------------------------------------------------------------------------------
Register for understanding the basic back end process for Stock Exchange: bit.ly/3eFD6LP
Use TAKEUFORWARD to unlock this event when live. For mobile users, you'll need to download the Unacademy App, so make sure thats' done before the event.
Please Please SUBSKRIIIBEEEEE the new channel: / @striver_79
---------------------------------------------------------------------------------------------------------------------------
Problem Link: practice.geeks...
C++/Java Code Efficient: takeuforward.o...
---------------------------------------------------------------------------------------------------------------------------
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_...
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgC...
---------------------------------------------------------------------------------------------------------------------------
If you appreciate the channel's work, you can join the family: bit.ly/joinFam...
✅Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: /
✅ Instagram: /
✅Connect with us: bit.ly/tufteleg... (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #ds #placements

Опубликовано:

7 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 208

@takeUforward 3 года назад

✅ Instagram: instagram.com/striver_79/ Please comment if you understand, a comments means a lot to me :)

@fardeenshaikh6434 3 года назад

Eid Mubarak

@jayadubey_22 3 года назад

bhaiyaa I was not able to understand the brute force approach solution of this at gfg please explain that also in some other problems

@rosansenapati-pl5hr Год назад

Striever why we don't use any of graph tarversal?

@shivamdashore6864 9 месяцев назад

Why TC will be M^N ?? it should be (M^N) * N, Because we traverse adjacency list as well in isSafe method everytime and maximum cost of adjList will be of N So. TC will be (M^N) * N @takeUforward

@lakhansingh_barod Год назад

Tried solving without looking at any explanation for the first time in this playlist, took me almost three hours but did it on my own❤

@arnobsaha7071 4 месяца назад

Do u just solved the algo or full. Coding

@lakhansingh_barod 4 месяца назад

@@arnobsaha7071 Full code

@tanayshah275 3 года назад

Heads up: If you are practicing on gfg the graphs are stored in a different manner for different programing languages. For c++ : in matrix For Java: in an adjacency list For Python : in matrix For Javascript : in matrix Just posting because when I started implementing with python I was access the graph as if it is an adjacency matrix and it was resulting in wrong submission so, I thought if anyone else is trying to do the same can save some time by not repeating my mistake.

@tanayshah275 3 года назад

posting python version of same code : def is_safe(node, c, graph, color, n): for i in range(n): if i != node and graph[i][node] == 1 and color[i] == c: return False return True def solve(node, graph, color, m, n): if node == n: return True for c in range(1, m + 1): if is_safe(node, c, graph, color, n): color[node] = c if solve(node + 1, graph, color, m, n): return True color[node] = 0 return False color = [0] * V return solve(0, graph, color, k, V)

@manasanand3531 3 года назад

I was looking for this problem explanation for the past few days but could'nt find a proper one. Now I can surely say, this one was the best amongst all. Thanks for this.🙌

@takeUforward 3 года назад

Thankyouu :)

@whocares7557 3 года назад

Good explanation like always, thanks🙂❤️ Wanted to get clarified of two things here: 🤔0. Isn't the complexity M^N, because there are N places to fill with M choices for each, so wouldn't M be multiplied N times making it M^N? 🤔1. We haven't considered the time complexity for checking the possibility of filling the color(isSafe), which can be of order N at worse, but shouldn't we?

@bharathkumar5870 2 года назад

total time (M^N)*N(issafe)

@whocares7557 2 года назад

@@bharathkumar5870 yes, that's what I thought it should be.

@parthsalat 2 года назад

@@bharathkumar5870 Yes, That's what I believe is correct

@shivamnegi7552 Год назад

@@bharathkumar5870 why not (M*N) ^ N ?

@upamanyumukharji3157 4 месяца назад

@@shivamnegi7552 yes checking will be taken for each color pick so (M*N)^N

@kamalkantrajput4431 3 года назад

time complexity = O(m ^ n) not o(n^m) thanks bhaiya . as we have m choice for each node .

@SJ_46 2 года назад

yes right

@shubhambhardwaj8894 3 года назад

Thank you brother! I'm preparing for my placements following your sde sheet and I'm getting so much confidence, please continue doing the great work 🙏👍

@tekken1935 3 года назад

how is the progress? Placed yet?

@jaydeepkadam Год назад

Sir placed? Please reply ✨

@human75788 2 года назад

I solved the problem myself just with your explanation upto 13 minutes. Thanks Striver. The way you spoonfeed us nobody does, it just stays in my head.

@ROSHANKUMAR-rl6bf 3 года назад

If the graph is connected simple dfs based recursion also works but one can only appreciate this if he wrote code for connected and realises if there are more than one components what should be done

@vankshubansal6495 3 года назад

True, I skipped this part. Attaching the DFS solution which handles all cases bool solve(int sv, bool graph[101][101], int V, vector& visited, int colors) { unordered_map visitedColors; for(int i = 0; i < V; i++) { if(graph[sv][i] == true && visited[i] != -1) visitedColors[visited[i]] = 1; } if(visitedColors.size() == colors) return false; for(int i = 0; i < colors; i++) { if(visitedColors[i] > 0) continue; visited[sv] = i; bool isAll = true; int j = 0; for(j = 0; j < V; j++) { if(graph[sv][j] == true && visited[j] == -1) { if(solve(j, graph, V, visited, colors) == false) break; } } if(j == V) return true; } visited[sv] = -1; return false; } bool graphColoring(bool graph[101][101], int m, int V) { vector visited(V, -1); for(int i = 0; i < V; i++) { if(visited[i] == -1) { if(solve(i, graph, V, visited, m) == false) return false; } } return true; }

@rishabhgupta9846 Год назад

@@vankshubansal6495 can you pls explain how your code is working?

@sowndaryav6680 3 года назад

U are doing a great job for students sir. Thank you so much for your efforts.

@mohitsingh7793 Год назад

Correction in Time-Complexity discussed in striver's vedio T.C = O(M^N)*N(isSafe-fxn) For one node ,we have m different colors. For n node we have m*m*m.....n times =M^N Also isSafe() takes O(N) in worst case. Let me know if I was wrong.

@tushar7305 Год назад

It N^m* N

@vegitogamingpubg3364 3 года назад

Very detailed and easy to understand explanation.. 10 times better than the so called paid courses.. Thank you so much bhaiya ❤

@Tomharry910 Год назад

Beautifully explained a tough problem very simply and in an easy to understand way. Thank you so much!

@devanshikapla7491 Год назад

Amazing explanation as well as the code. I haven't seen so much clear explanation on any other channel. Thankyou for this❤️

@98ujaal Год назад

Correction: Time complexity is O(M^N) not O(N^M) (which solves the P vs NP problem and he would have been a millionaire by now)

@priyanshudwivedi7535 9 месяцев назад

What do you mean by him being a millionaire?

@shivammishra6381 22 дня назад

@@priyanshudwivedi7535 P vs NP problems are problems can truly revolutionize the world of computing and maths. and have reward of a million dollars for the person who solve them.

@Rohan-hj9gg 3 года назад

The time complexity has to be M^N ? Because the height of tree will go till N and for each node we have M choices.

@soumavanag5025 3 года назад

correct, it confused me

@rncsMahimaMahendru 3 года назад

even i think so

@nitinvadadoriya8280 Год назад

Small Correction In Time Complexity T.C = ~M^N not N^M Because we have M-Color choice for every nodes. Tell me am i correct or not..

@AdityaRajVerma-io3pr 7 месяцев назад

i was not able to draw the recursion tree, now as I understood the approach, I just coded it by myself, thanks bhaiya

@sasirekhamsvl9504 3 года назад

The best explanation I have found on youtube. Thank you so much.

@ashutoshkumawat7854 3 года назад

I Think it's Complexity is M^n because m is no.of choice like it happen in printing all sub sets 2^n.......please correct me if i'm wrong

@stith_pragya 4 месяца назад

Understood............Thanks a ton for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

@pranavpandey4331 3 года назад

I think the time complexity should be O(m^N)

@sharmaji490 3 года назад

Yupp it will be

@reshubnigam8375 3 года назад

How do we get the intuition that here we had to traverse serially on the nodes and not initiate dfs for every connected component? Had been doing that and got stuck at what the base case would be for dis-connected components as backtracking was erasing everything :|

@RahulKashyap-yv5ox 3 года назад

Yes I was also stucked at the same point

@aditya-bl5xh 3 года назад

Shuru majburi mei kiye the ab mazza aa rha hai...

@janaSdj 3 месяца назад

One more optimization,if m>=4 then it is always possible to colour a graph by 4 colour theorem. So if m>=4 return true.

@BookJournalWithMimansa 2 месяца назад

Hi All, I was really confused between M coloring problem and bi partite graph problem. The Bi partite graph problem uses DFS/BFS for checking if no 2 adjacent nodes are filled with the same color(2 colors). So I was wondering if we could use DFS/BFS here as well. Turns out no, as in the GFG practice problem, in one TC. we have disconnected nodes as well in the graph and this cant be covered with DFS/BFS. Please let me know if my understanding is correct.

@factfactorial632 2 года назад

I have doubt , time complexity should be N*(N^m) because we have that IsSafe function also there and at max a node can be connected to all the others node So O(N) for chacking btw Great explanation

@tushar7305 Год назад

Yes it should be there

@mehershrishtinigam5449 Год назад

@@tushar7305 that will just be O(N^(m+1)) which will be O(N^m) only, i think?

@mohammedwaseem8599 3 года назад

Hello bhaiya i hope you are doing extremely well

@snehagoyal4978 Год назад

Thank you striver, after watching your previous videos of this playlist, I could do this on my own;

@adrikagupta5573 3 года назад

Great video! I have one doubt though. Shouldn't the time complexity be O(m^N)?

@abhinavpandey3356 3 года назад

Can u explain why n^m seems correct as for every node there are m possibility

@sparshsharma6068 2 года назад

@@abhinavpandey3356 Here's how i devised the TC for this: At each node, there will be at max there will be m operations and for each operation on a node, their childs will have their own respective m operations. i.e if a graph was: 1 / \ 2 3 then at node 1 there will be m operations but for each operation on node 1, there will be m operations on its successive nodes(here on the node 2 and then on node 3). i.e m*m*m = m^3 == m^n thus on graphs having n nodes, starting from source node, there will be: m*m*m*...........*m(n terms) == m^n. Thus, TC will be O(m^n). I hope it helps!

@PiyushSharma-bo6pp 2 года назад

@@abhinavpandey3356 easy o(n) approach is there

@Pawan_Kumar_Mehta 2 года назад

Yes yr right cause the height of the tree will be N and at each level of rec we will have m nodes.

@parthsalat 2 года назад

Yes, imo that should be the correct time complexity

@omkarsawant9267 8 месяцев назад

C++ Code for M coloring Problem--> TC-- M^V v is no of vertices and M is max no if colors that can be used. Exponential TC due to Recursive nature of algorithm SC-- O(V) as color vector stores color assigned to each vertex. Size is proportional to no of vertices in the graph.But it is at most O(V) due to depth of recursion. ----- Code Follows ------ #include #include using namespace std; class Graph { private: int V; // No of Vertices vector adj; // adjacent list; public: // constructor Graph(int Vertices) : V(Vertices), adj(Vertices) {} // Funciton to add an edge to the graph void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // func to check if it is possible to color the graph with at most M colors bool graphColoring(int M); private: // utility function for graph coloring; bool graphColoringUtil(int vertex, vector &color, int M); }; bool Graph :: graphColoringUtil(int vertex, vector &color, int M) { // check if we have assigned colors to all vertices if (vertex == V) return true; // try assigning different colors to current vertex for (int c = 1; c

@abhisheksa6635 10 месяцев назад

Badhiya bhai, woh tumney strategy same rakha h parallel recursion wala and saarey backtracking solve kar liye.

@abhinavpandey3356 3 года назад

What if I don't put colour [node]=0 Does it affect anything ,as I'm looking colr of negbour node to match with the colr I'm am trying to color for a particular node for deciding it's color

@sohamsonwane1534 3 месяца назад

The best what you get i have done the recursion and backtracking from another paid courser but it is not worth it but the striver recursion playlist is bast of class i have done all recursion from 1 to last and now the recursion feel like game not very easy but so far so good

@sahelidebnath9972 Год назад

For adjacency list, shouldn't we check: public boolean isColorPossible(int node, int length, int colorTochoose,boolean graph[][], int[] color ) { for(int i=0;i

@animearena8443 2 года назад

python code for anyone struggling with it: def graphColoring(graph, k, V): color=[0]*V def mcolor(vertex,graph,k,V): if vertex==V: return True for i in range(1,k+1): flag=1 for j in range(V): if graph[vertex][j]==1 and color[j]==i: flag=0 break if flag==1: color[vertex]=i if mcolor(vertex+1,graph,k,V): return True color[vertex]=0 return False return mcolor(0,graph,k,V)

@riyakumari8377 Год назад

hey can u tell me why are we doing => graph[vertex][j]==1 ?

@nirupamsuraj1634 Год назад

@@riyakumari8377to check if the node j is connected to vertex node

@sanjana-singla Год назад

Can't we just count the maximum number of adjacent nodes present in the graph? if the maximum nodes is greater than the number of colors, return false, else return true?

@akshitkathuria3516 Год назад

I had the same thought and tried applying it on the bipartite graph problem but one test case failed which is this one: [[4,1],[0,2],[1,3],[2,4],[3,0]] Here every node has 2 adjacent but we still cannot color the graph using 2 colors. So i think it wont work for this problem as well

@narayanbung7550 3 года назад

Your videos make problem look very simple.Thanks

@rishukumarsingh3926 Год назад

In this problem, we are trying every color, if and only if the color is possible to take, i.e. we are filtering and taking, we are not waiting to mismatch!

@vaishnavi5070 2 года назад

shouldn't the graph be List where every index is considered as node and the list that is there in that index are the adjacent nodes??

@RitikKumar-lv8cm 2 года назад

hi in this problem we can not simply check for each node. instead we must create adjacent node for each node and then check for possibility of coloring

@bitturanjan9539 3 года назад

Great explanation man❤️

@vishnuthulasidosss Год назад

I wonder why the BFS solution is not working! Could you tell me what's wrong with BFS?

@madhurgupta4220 2 года назад

A Detailed And A Great Explanation .

@shwetabhagat8920 Год назад

you make all the problems easy⭐

@supratimbhattacharjee5324 3 года назад

Best explanation....learning for my practical exams

@rishurana9655 2 года назад

This question is exactly similar to n queen problem for those who have problem can first try that one and then come to this question

@nakuljindal1421 2 года назад

Bro why we have backtracked in this as for loop itself change its colour suppose if statement gives u false then ultimately it will go to another colour why does it makes difference whether we have done 0 previously or not

@lettry5297 3 года назад

Thanks you sir for this video. Sir can you please clarify whether for SDE profile it is mandatory to know C++ or Java ? Python is not sufficient for cracking test , I am practicing with Python only? Sir please guide..... 🤷‍♂️

@user-oj2wg8og9e Год назад

Wonderful explanation sir!! Thank you !!!

@kannupriyarana4971 3 года назад

clear and straight-forward explanation. Thanks bro :)

@fardeenshaikh6434 3 года назад

Eid Mubarak striver Bhai

@takeUforward 3 года назад

Eid mubarak bhai ❤️

@prasannapm3220 2 года назад

Amazing thought process sir !!

@siddharthvs1770 3 года назад

Can we not use a greedy approach for this problem? Would it fail, if yes why?

@techfreak416 2 года назад

why do we have to check all possible safe colors for every node? why cant we just assign any 1 of the colors which are not adjacent to current node.

@nopecharon 2 года назад

Do i need to learn graphs for this problem?

@gunanka6860 2 месяца назад

again solved on my own even without the explanation... i think im getting better : ")

@parthsalat 2 года назад

Thanks

@skyy-v5o 8 месяцев назад

Hello striver , I see there are no articles linked to bit manipulation , linked list problems . Plus there are no javascript code on striver website .

@paragroy5359 3 года назад

Thanks for the playlist sir......it's really helpful

@sahelidebnath5085 7 месяцев назад

Time complexity will be O(M^N) isn't it? (worst case)M colors for every node(N).

@aloklaha8694 2 месяца назад

Thanks brother. Understood

@083_h_nitishkumarjha3 Год назад

why we are calling the function for next serial node, shouldn't we call for the nodes attached to this node ?

@shivanshkhare2724 2 года назад

After watching this series , I understood why striver is god of coding.

@dibyajyotibhuyan6111 2 года назад

Hello Everyone, Can any one tell me that why k!=node is required in issafe function in c++ code ?

@mohakhiphop Год назад

Code will work fine without that (k!=node) , as in the case when (k == node) , graph[k][node] will always be 0 i.e the node itself which obviously can't be neighbour of itself

@chase.2595 11 месяцев назад

isnt time complexity m^n? as m choices of colour available in n recursive calls?

@josephstark5810 Год назад

i think we cant do it by graph traversal beacause it give tle in case of cycle and also hard to manage backtracking right?

@Ace-ex9gg Год назад

explanation is good but time complexity is (n-1)*m^n by the way.

@gouravkumarshaw417 2 года назад

thanks!!

@K_EN_VisheshSaini 2 года назад

I havent done Graphs yet, do i need to know graphs for this question or Recursion is sufficient alone?

@gauravagrawal7988 Год назад

You should have very basic knowledge of graphs for this

@viswanathank2551 3 года назад

thanks for the best explanation in yt

@rishukumarsingh3926 Год назад

Why in this problem, we didn't follow standard dfs and used as node numbers as a part of traversal?

@nipunrawat7137 Год назад

same doubt

@PrashantSingh-jy6zp 3 года назад

for skip ads go to 4:01

@ritugoyak7238 3 года назад

Thank you so much sirr

@VikashKumar-tr9cq 2 года назад

will this algorithm work if there is more than one connected components?

@ratankumar1399 2 года назад

can you make some videos on BFS approach of this ques ,its bit confusing for me

@riteshadwani9084 Год назад

Amazing explanation!

@dipjoybasak3156 3 года назад

Brother cant we just check for bipartiteness of the graph? Like if it is bipartite, we can always color using m>=2 and if its not then anything m>=3... Wont this work?

@nameetjain2251 3 года назад

Exactly what i was thinking.

@sharmaji490 3 года назад

Consider when you are asked to tell if a graph can be colored using 5 colours and suppose it is not biparatite. Then what will you return. You are not sute about 3,4,5 colors. So only checking biparatiye won't work every time. Hope it is helpful in some way

@sharmaji490 3 года назад

If a graph is not paratite m>=3 might work

@ravindermaan1887 Год назад

Time Complexity: O(M^N).

@kavyabanka4482 Год назад

can someone tell me why we have taken G[node] in for loop for(int it:G[node]){ //Here y we have taken G[node] i m stuck here please clarify my doubt someone.

@ganeshkamath89 2 года назад

I have 1questions: 1) For Java you are just checking 1 condition in the loop if (color[it] == col) return false; 2) Whereas in C++ you are checking multiple conditions: if (k != node && graph[k][node] == 1 && color[k] == col) Is this because you have done some preprocessing in Java to have graph as an adjacency list but are passing the graph itself in C++?

@SanthoshSunny21 2 года назад

In cpp he used adjacency Matrix nd in Java adjacency list In Matrix you will check if there is an edge with every other vertex (g[i][j]==1) but in adjacency list only edges are present so no need to check if there's an edge

@ganeshkamath89 2 года назад

@@SanthoshSunny21 Thanks

@parthsalat 2 года назад

C++ code starts at 20:53

@UECAshutoshKumar Год назад

Thank you sir

@amanupadhyay1275 3 года назад

"Definitely" some great stuff Striver. Thanks a lot.

@deepanshipandey2148 9 месяцев назад

@takeUforward Why does this code give me a wrong ans? bool graphColoring(bool graph[101][101], int m, int n) { vector color(n, 0); for(int i=0;i

@raviashwin1157 3 года назад

God level explanation🔥....really appreciate your efforts❤️....what was that song in the end??

@aasthajha1051 3 года назад

explanation ek no.!!!!!!!!!!!!!!!!!

@sahilnegi2789 3 года назад

Thanks bro for amazing content .

@kunalsurya1158 Год назад

i think the time complexity would be M^N where m is color and N is node bcz the equation is T(n) = MT(n-1) + C

@bhaveshkumar6842 2 года назад

Thank you!

@anshulgoel1940 Год назад

Will the time complexity be N^M or M^N ?

@chase.2595 11 месяцев назад

i think m^n m choices in n rec calls right?

@faisalazmi8953 3 года назад

Understood, valuable content

@tejendrapalsingh9176 2 года назад

approach i tried, we atmost need 3 color to color a graph , so check first if it is a bipartite , if yes then true if not , then check if color>=3 , if yes then true , else false

@ankursharma6084 2 года назад

There is some issue in the time complexity. For all the m choices we are taking o(n) time to verify is safe property. So , Tc should be (m*n)^n. @take U forward can you please verify.

@SatyamKumar-rq3kr 2 года назад

Yes bro now even the god can't reject this complexity, interviewer kya hi kr lega BTW it's(m^n)*n checking is_safe function☠

@SatyamKumar-rq3kr 2 года назад

1 month ago WoW bro aap kafi aage chate ho hamesha🙂

@sathishkumar-dc9ce 3 года назад

Great job anna.. luv from TN 😍

@sahiljain2524 3 года назад

Bhaiya Time complexity M^N ayegi na ?

@takeUforward 3 года назад

Hnn

@sahiljain2524 3 года назад

@@takeUforward Ok bhaiya

@factfactorial632 2 года назад

@@takeUforward Bhaiya it should be N*(N^m) because we have that IsSafe function also there and at max a node can be connected to all the others node So O(N) for chacking

@anishraj66 Год назад

i think time complexity will be m^n since each fxn is calling m another fxn so... m*m*m*m*.....n times

@nikhilprasad644 2 года назад

bro i have a serious doubt. Thought this for hours but couldn't find a way. i tried solving the problem by visiting the neighbours(in ur case its going linearly until u reach the number of nodes) but its giving wrong answer after submitting on gfg practice problem. Can u pls solve it by visiting the neighbours, or is there a reason why my method will not work. Thanks bro.

@sanyattaneja8551 Год назад

It wont work if graph is disconnected eg 1-2 3-4 edges now you can't move to 3 from 2 If graph is fully connected then i think this code works bool check(int node , vector adj[] , int x , int colour[]){ for(auto it : adj[node]){ if(colour[it] == x) return false ; } return true ; } bool helper(int ind , vector adj[] , int col , int &m,int colour[]){ colour[ind] = col ; //check neighbours colour for(auto it : adj[ind]){ int neigbOfInd = it ; if(colour[neigbOfInd] != -1) continue ; for(int x = 0 ; x < m ; x++){ if(check(neigbOfInd,adj,x,colour)){ if(helper(neigbOfInd,adj,x,m,colour)) return true ; colour[neigbOfInd] = -1 ; // colour[in] } } return false ; } return true; } bool graphColoring(bool graph[101][101], int m, int n) { vector adj[n] ; for(int i = 0 ; i < n ; i++){ int node = i ; for(int j = 0 ; j < n ; j++){ if(graph[i][j]) adj[node].push_back(j) ; } } int colour[n] ; for(int i = 0 ; i < n ; i++) colour[i] = -1 ; // return 1 ; for(int x = 0 ; x < m ; x++){ if(helper(0,adj,x,m,colour)) return 1 ; } return 0 ; }